//汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。 
//
// 沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽
//油。 
//
// 假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。 
//
// 当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。 
//
// 为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。 
//
// 注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。 
//
// 
//
// 示例 1： 
//
// 输入：target = 1, startFuel = 1, stations = []
//输出：0
//解释：我们可以在不加油的情况下到达目的地。
// 
//
// 示例 2： 
//
// 输入：target = 100, startFuel = 1, stations = [[10,100]]
//输出：-1
//解释：我们无法抵达目的地，甚至无法到达第一个加油站。
// 
//
// 示例 3： 
//
// 输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
//
//输出：2
//解释：
//我们出发时有 10 升燃料。
//我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
//然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
//并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。
//我们沿途在1两个加油站停靠，所以返回 2 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= target, startFuel, stations[i][1] <= 10^9 
// 0 <= stations.length <= 500 
// 0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < 
//target 
// 
// Related Topics 堆 动态规划 
// 👍 123 👎 0

package com.leetcode.editor.cn;

import java.util.PriorityQueue;

//Java：最低加油次数
class P871MinimumNumberOfRefuelingStops {
    public static void main(String[] args) {
        Solution solution = new P871MinimumNumberOfRefuelingStops().new Solution();
        // TO TEST
//        int[][] stations = {{10, 60}, {20, 30}, {30, 30}, {60, 40}};
//        System.out.println(solution.minRefuelStops(100, 10, stations));
//        int[][] stations = {{25, 25}, {50, 25}, {75, 25}};
//        System.out.println(solution.minRefuelStops(100, 25, stations));
//        int[][] stations = {{47, 220}, {65, 1}, {98, 113}, {126, 196}, {186, 218}, {320, 205}, {686, 317}, {707, 325}, {754, 104}, {781, 105}};
//        System.out.println(solution.minRefuelStops(1000, 83, stations));
//        int[][] stations = {{22, 17}, {100, 23}, {121, 71}, {141, 77}, {236, 4}, {438, 78}, {500, 76}, {642, 66}, {672, 20}, {685, 81}};
//        System.out.println(solution.minRefuelStops(1000, 83, stations));
        int[][] stations = {{13, 21}, {26, 115}, {100, 47}, {225, 99}, {299, 141}, {444, 198}, {608, 190}, {636, 157}, {647, 255}, {841, 123}};
        System.out.println(solution.minRefuelStops(1000, 299, stations));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minRefuelStops(int target, int startFuel, int[][] stations) {
            if (startFuel >= target) {
                return 0;
            } else if (stations.length == 0) {
                return -1;
            }
            if (startFuel < stations[0][0]) {
                return -1;
            }
            //加油次数
            int ans = 0;
            //起点到上一个加油站的距离
            int prev = 0;
            //当前剩余油量
            int currFuel = startFuel;
            //大顶堆
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int[] station : stations) {
                int l = station[0];//当前加油站到起点距离
                int fuel = station[1];//当前加油站油量
                currFuel -= (l - prev);
                while (currFuel < 0 && !queue.isEmpty()) {
                    //从已经经过的加油站中,找最大的加油
                    currFuel += queue.poll();
                    ans++;
                }
                if (currFuel < 0) {
                    //说明前边的加油站的全部油量，不足以行驶到下一个加油站
                    return -1;
                }
                queue.offer(fuel);
                prev = l;
            }
            currFuel -= (target - prev);
            while (currFuel < 0 && !queue.isEmpty()) {
                //从已经经过的加油站中,找最大的加油
                currFuel += queue.poll();
                ans++;
            }
            if (currFuel < 0) {
                return -1;
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}